πŸ’‘ 이뢄 탐색(Binary Search)

@Seongukbaek Posted May 05, 2022 Β· Updated May 05, 2022 Β· 3 min read

🧷 이뢄 탐색

탐색 λ²”μœ„λ₯Ό 두 λΆ€λΆ„μœΌλ‘œ λΆ„ν• ν•˜λ©΄μ„œ μ°ΎλŠ” 방식

  • μ²˜μŒλΆ€ν„° λκΉŒμ§€ νƒμƒ‰ν•˜λŠ” 것보닀 더 λΉ λ₯Έ μ‹œκ°„ λ³΅μž‘λ„λ₯Ό κ°€μ§€λŠ” 방식
**μ‹œκ°„ λ³΅μž‘λ„** 전체 탐색: O(N) 이뢄 탐색: O(logN)

πŸͺš κ³Όμ •

κ°€μž₯ 핡심은 정렬이 λ˜μ–΄ μžˆμ–΄μ•Ό ν•œλ‹€λŠ” 점이닀.

  • left 와 right λ₯Ό μ‚¬μš©ν•΄ mid λ₯Ό μ„€μ •ν•œλ‹€.
  • mid 와 κ΅¬ν•˜κ³ μž ν•˜λŠ” 값을 λΉ„κ΅ν•œλ‹€.

    • κ΅¬ν•˜κ³ μž ν•˜λŠ” 값이 더 큰 경우, left = mid + 1
    • 더 μž‘μ€ 경우, right = mid - 1
  • left > right κ°€ 될 λ•ŒκΉŒμ§€ 반볡
  • 탐색할 λ°°μ—΄μ˜ λ²”μœ„λ₯Ό λ²—μ–΄λ‚œλ‹€λ©΄, κ΅¬ν•˜κ³ μž ν•˜λŠ” 값이 배열에 μ—†μŒμ„ νŒλ‹¨ν•  수 μžˆλ‹€.
int binarySearch(int[] numbers, int M) { Arrays.sort(numbers); int left = 0; int right = numbers.length - 1; int mid; while (left < right) { mid = (left + right) / 2; if (numbers[mid] == M) return mid; else if (numbers[mid] < M) left = mid + 1; else right = mid - 1; } }

πŸͺš μΆ”κ°€ 예제

이뢄 탐색은 μ •λ ¬λœ λ°μ΄ν„°μ—μ„œ νŠΉμ • 값을 찾고자 ν•  λ•Œ λΉ λ₯Έ μ‹œκ°„ λ³΅μž‘λ„λ‘œ 탐색이 κ°€λŠ₯ν•˜λ‹€λŠ” μž₯점이 μžˆλ‹€. 이λ₯Ό μ΄μš©ν•΄ μ •μˆ˜ N이 μ£Όμ–΄μ‘Œμ„ λ•Œ, N의 μ œκ³±κ·Όμ„ κ΅¬ν•˜λŠ” μ½”λ“œλ₯Ό μž‘μ„±ν•΄λ³Έλ‹€.

  • 1λΆ€ν„° μ£Όμ–΄μ§„ μ •μˆ˜κΉŒμ§€μ˜ λ‹¨μˆœ 반볡 및 ν™•μΈμœΌλ‘œ ꡬ할 μˆ˜λŠ” μžˆμ§€λ§Œ μ΄λŠ” O(N)O(N)의 μ‹œκ°„ λ³΅μž‘λ„λ₯Ό κ°€μ§„λ‹€.

이λ₯Ό 이뢄 탐색을 μ‚¬μš©ν•˜μ—¬ "0λΆ€ν„° NκΉŒμ§€μ˜ μžμ—°μˆ˜ 쀑 N의 제곱근이 μžˆλŠ”μ§€ μ—†λŠ”μ§€" ν™•μΈν•˜λŠ” μ½”λ“œλ‘œ λ³€κ²½ν•œλ‹€. 즉, 0λΆ€ν„° NκΉŒμ§€μ˜ μ •λ ¬λœ μžμ—°μˆ˜ μ€‘μ—μ„œ νŠΉμ • 값을 μ°Ύκ³  μžˆλŠ” 것이닀.

int squareRootSearch(int M) { int left = 0; int right = M; int num, squareNum; while (left < right) { num = (left + right) / 2; squareNum = num * num; if (squareNum == M) return num; else if (squareNum < M) left = num + 1; else right = num - 1; } }

πŸ“• μ°Έκ³ 

@Seongukbaek
배우고 μ •λ¦¬ν•˜κ³  κ³΅μœ ν•˜λŠ” λŒ€ν•™μƒ λ°±μ„±μš±μž…λ‹ˆλ‹€ πŸ˜€